Bilkent University
Department of Computer Engineering

---

S E M I N A R

 

Algorithms for VPN Tree Maintenance in the Hose Model

 

İskender Yakin
MSc.Student
Computer Engineering Department
Bilkent University

Virtual Private Networks(VPNs) have emerged as cost effective alternatives to private networks constructed with dedicated lines. Among the two models proposed for provisioning VPNs, the Hose model became more popular than the pipe model because it enables customers to have easier and flexible specification beside enabling ISPs to reduce cost due to easy characterization and multiplexing gains. To exploit the multiplexing gain of the Hose model, tree structures have been proposed for provisioning and [KRSY] have proposed novel algorithms for computing the optimal VPN tree which are particularly effective for the symmetric case where ingress and egress bandwidths of each VPN host are equal. In this paper, we present novel adaptive algorithms to enable VPN trees in the Hose model supporting dynamic membership changes. Given a VPN tree we consider optimal insertion and deletion of VPN end-points to and from the tree one by one or in batches while preserving the links of the existing tree.The optimality criteria is minimization of the total reserved bandwidth of the new VPN tree. We will consider both incapacitated (i.e., links have infinite capacity) and capacitated versions of the problem. The algorithms we present for the incapacitated case make optimal single-node insertion in O(M + N ) time, optimal single node deletion in O(R) time and optimal batch insertion in O(M N + |J||TL^m|N ) time where M and N are number of edges and nodes in the network, R is the radius of the VPN tree,|J| is the number of VPN endpoints to be inserted and |TL^m| is the number of nodes in the VPN tree. For the capacitated case we have linear time algorithms for single node insertion and deletion with time complexities O(M + N ) and O(R) respectively while we show that optimal batch insertion of VPN endpoints is NP-hard. We also show that competitive ratio of any adaptive insertion algorithm is at least 1 + 1/2.

 

DATE: November 13, 2006, Monday@ 15:40
PLACE: EA 409